1. Field of the Invention
The invention relates in general to a system for determining positions for device modules within an analog integrated circuit (IC) and in particular for a system for positioning device modules within an IC containing symmetric circuits.
2. Description of Related Art
A netlist describes an analog IC as including a set of interconnected device modules such as transistors, capacitors, resistors and other devices. A computer-based placement tool processes a netlist to determine a suitable position and orientation within the IC for each device module. To reduce the effect of parasitic mismatches and circuit sensitivity to thermal gradients or process variations, a placement tool will try to place pairs of matching device modules close to one another and symmetrically with respect to one another with respect to a common axis. The circuit designer will normally provide the placement tool with a set of symmetry constraints identifying each group of device modules (a “symmetry group”) that is to have a symmetric layout, identifying each pair of matching devices (a “symmetry pair”) within each symmetry group that is to be placed symmetrically about an axis of the symmetry group, and identifying each internally symmetric device module (a “self-symmetry device module”) within the group that is to be centered on the symmetry group axis. The circuit designer also will provide the placement tool with a set of device matching and proximity constraints.
When generating a placement plan, a placement tool typically treats each device module of an IC as a rectangle that is large enough to accommodate the device module and to provide some additional space around the device module for routing the conductors (“nets”) that are to interconnect device modules. The problem of selecting a position for each device module of the IC becomes one of finding a non-overlapping position within a plane for each of a set of rectangles of various sizes and shapes in a way that satisfies various matching, symmetry, proximity and other constraints on device module placement.
FIG. 4 shows a placement for a symmetry group that is symmetric about a vertical axis 10 and FIG. 5 shows a placement for a symmetry group that is symmetric about a horizontal axis 12. The following notation is used in FIGS. 4 and 5 and elsewhere in this specification.
S a symmetry group
bi a device module
(bi, bi′) a symmetry pair
bis a self-symmetry device module
The following expression can represent the symmetry group S of FIG. 4:S=((b1,b1′),(b2,b2′),b3s)
A “device matching constraint” forces a common gate orientation and an interdigital placement on a group of devices. Any group of devices subject to a device matching constraint is called a “matching group” and a placement tool can recognize a matching group within a netlist when devices types, sizes and interconnections match a predetermined pattern. FIG. 1 is a schematic diagram of an example two-stage operational amplifier including a set of transistors M1-M9, and a capacitor C1. FIG. 2 illustrates an inter-digitized type placement of a matching group formed by transistors M3 and M4 of FIG. 1. FIG. 3 Illustrates a common-centroid type placement of a matching group formed by transistors M1 and M2 of FIG. 1.
A “proximity constraint” limits a particular group of devices to a connected placement with the devices placed near one another, for example, so that they share a common substrate/well region, so that they are surrounded by a common guard ring, or so that they can be interconnected by short wire. A group of devices subject to a proximity constraint is called a “proximity group”. For example, FIG. 9 illustrates a placement of a PMOS proximity group 14 sharing a common N-well 15 and an NMOS proximity group 16 formed in a p-substrate 17. Proximity groups may be hierarchical. For example, proximity groups 14 and 16 of FIG. 9 can be designated as a higher-level proximity group to ensure they are placed near one another when the two lower-level proximity groups must be interconnected by short wires.
A placement plan for an analog IC must satisfy other constraints in addition to symmetry constraints including, for example, constraints on available space and constraints on positions and orientations of certain device modules. Although many different IC placements may satisfy all constraints, designers consider some placements to be better than others based on a number of factors. For example, designers usually consider a placement that positions highly interconnected device modules near one another to be better because it reduces the lengths of the net needed to interconnect device module terminals, thereby making it more likely that a computer-based routing tool will be able to route the nets between device modules positioned in accordance with the placement plan. A more compact placement may be considered better when it can result in a smaller or faster IC. Placement tools commonly generate several different trial placements and evaluate each trial placement based on a “cost function” having a value that is a weighted sum of various attributes of the trial placement such as variables representing estimated lengths of the nets (“wire lengths”), the total placement area and other factors. The trial placement having the lowest cost function value is selected as the most suitable placement.
One way to generate a large number of trial placements is to start with an initial placement and then iteratively perturb the initial placement by changing positions and orientations of the device modules to produce many trial placements, and to evaluate a cost function for each trial placement to find a best placement. Much prior work in this area has been directed toward developing approaches for reducing the amount of processing time needed to arrive at a low cost placement solution while satisfying the symmetry constraints.
One way to reduce processing time is to represent a trial placement in a way that allows a placement tool to quickly and easily perturb a trial placement to produce a different placement. While it is possible for a placement tool to employ a topological representation of a trial placement that directly tracks the coordinates of each rectangle within an IC layout, it is difficult and time-consuming for a placement tool to iteratively perturb such a topological representation of a trial placement in order to create other trial placements because a change to coordinates of any one rectangle can have a ripple effect on coordinates of every other rectangle. The article, “B*-Trees: A New Representation For Non-slicing Floorplans,” Proc. DAC, pp. 458-463, 2000, describes a placement method employing a binary tree (“B*-tree”) to represent a compacted placement in which no device module can move any further down or to the left. A B*-tree is a convenient way for a placement tool to represent a placement because it is relatively easy for the tool to alter a placement by altering the B*-tree representation. FIG. 12 shows a compacted placement of a set of 10 device modules b0-b9 and FIG. 13 shows a corresponding B*-tree representation of that placement wherein every node ni of the B*-tree corresponds to a device module bi of the compacted placement. The root n0 of the B*-tree of FIG. 2B corresponds to the device module b0 on the bottom-left corner of the placement of FIG. 12. For each node ni corresponding to a device module bi, the left child of node ni represents the lowest, adjacent device module on the right side of device module bi, while the right child of node ni represents the first device module above bi having the same horizontal coordinate within the placement plane. (Herein we refer to the “horizontal” direction in an IC placement plan such as that depicted in FIG. 12 as being directed toward the left and right sides of the figure and to the “vertical” direction as being directed toward the top and bottom of the figure.) The width and height dimensions (wi, hi) of the rectangular device module bi associated with each node ni can be stored in a database.
Given a B*-tree representation of a compacted placement, a placement tool can, when necessary, calculate the coordinate (xi, yi) of each device module through an ordered tree traversal. Suppose the device module bi, represented by the node ni, has the bottom-left coordinate (xi, yi), width wi, and height hi. Then for the left child, nj, of ni, xj=xi+wi; for the right child, nk, of ni, xk=xi. A placement tool in accordance with the invention maintains a contour structure to calculate y-coordinates. Thus, starting from the root node, whose bottom-left coordinate is (0, 0), then visiting the root's left subtree, and then its right subtree, the tool can use a pre-order tree traversal procedure (B*-tree packing) to calculate all coordinates of the device modules in the placement.
A B*-tree is a convenient way for a placement tool to represent a compacted trial placement that allows it to quickly perturb a trial placement by modifying its B*-tree representation and to quickly determine whether the placement satisfies some kinds of constraints by processing its B*-tree representation. For example it is possible to determine from a B*-tree representation whether a set of device modules forming a symmetry group will satisfy symmetry constraints on the symmetry group. Once a placement tool has generated a B*-tree representation of a new trial placement and has processed the B*-tree representation to determine whether the trial placement it specifies will satisfy various symmetry and other constraints, the placement tool can quickly convert the B*-tree representation of the trial placement into physical locations that will enable it to conveniently determine whether the trial placement satisfies other constraints and to evaluate the cost function for that particular trial placement. However, a placement tool employing B*-tree placement representations can still require substantial amounts of processing time to find an optimal placement particularly for large analog ICs that include several symmetry groups because the solution space that must be searched can still be quite large.
U.S. Pat. No. 6,550,046, issued Apr. 15, 2003 to Balasa et al describes an automated method for packing cells in an analog IC layout including symmetry groups that are subject to symmetry constraints. Symmetry constraints are defined for each symmetry group, which are represented by sequence-pairs. To reduce the solution space, the initial sequence pair encoding is required to be symmetry-feasible so that the search subspace is therefore limited to symmetry-feasible sequence-pairs. Nevertheless, the solution space is also quite large because the sequence-pair representation does not preclude the devices in symmetry groups from being placed far apart, which will not be considered a good placement.
What is needed is an approach to analog IC placement that limits the search space to trial placements wherein device modules forming each symmetry group reside near one another and wherein each symmetry group satisfies all symmetry constraints.